
// 239.滑动窗口最大值
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        // 用一个栈来维护最大值
        int n = nums.size() , l = 0  ,r = 0;
        deque<int> st;
        for( ; r < k ; r++) 
        {
            while(st.size() && nums[r] > st.back()) st.pop_back();
            st.push_back(nums[r]);
        }
        vector<int> ret{st[0]};
        for( ; r < n ; r++)
        {
            if(nums[l++] == st[0]) st.erase(st.begin());
            while(st.size() && nums[r] > st.back()) st.pop_back();
            st.push_back(nums[r]);
            ret.push_back(st[0]);
        }
        return ret;
    }
};